package tree

// https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
// 有序数组 转 平衡搜索树
// 算法: 二分
// 时间复杂度: O(n)
func SortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	head := new(TreeNode)
	makeBSTTree(head, nums)
	return head
}

func makeBSTTree(head *TreeNode, nums []int) {
	mid := len(nums) / 2
	head.Val = nums[mid]
	if mid > 0 {
		head.Left = new(TreeNode)
		makeBSTTree(head.Left, nums[:mid])
	}
	if mid < len(nums) - 1 {
		head.Right = new(TreeNode)
		makeBSTTree(head.Right, nums[mid+1:])
	}
}

